package com.tree.leetcode.array;

/**
 * @ClassName com.tree.leetcode.array
 * Description: 53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。



示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

 * <使用说明>
 * </p>
 * @Author tree
 * @Date 1/26/24 11:39 PM
 * @Version 1.0
 */
public class MaxSubArray_53 {
    public static void main(String[] args) {
        int[] nums = new int[] {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray1(nums));
    }

    /**
     *     贪心算法， 只要count < 0 , 则再加后面的数一定是拖累， 所以这种情况就直接抛弃， 重新开始计算
     */
    public static int maxSubArray1(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int count = 0;
        //注意这里要取最小的值
        int sum = Integer.MIN_VALUE;
        for (int i = 0; i< nums.length; i++){
            count += nums[i];
            // 取区间累计的最大值（相当于不断确定最大子序终止位置）
            sum = Math.max(sum, count);
            //只要 count < 0
            if(count < 0) count = 0;
        }
        return sum;
    }

}
